package sortedset

import (
	"math/bits"
	"math/rand"
)

const maxLevel = 16

type Element struct {
	Member string
	Score  float64
}

type node struct {
	Element
	backward *node
	level    []*level
}

type level struct {
	forward *node
	span    int64
}

type skiplist struct {
	header *node
	tail   *node
	length int64
	level  int16
}

func makeNode(height int16, score float64, member string) *node {
	n := &node{
		Element: Element{
			Score:  score,
			Member: member,
		},
		level: make([]*level, height),
	}
	for i := range n.level {
		n.level[i] = &level{}
	}
	return n
}

func makeSkiplist() *skiplist {
	return &skiplist{
		level:  1,
		header: makeNode(maxLevel, 0, ""),
	}
}

func randomLevel() int16 {
	total := uint64(1)<<uint64(maxLevel) - 1
	k := rand.Uint64() % total
	return maxLevel - int16(bits.Len64(k+1)) + 1
}

func compare(s1 float64, s2 float64, m1 string, m2 string) bool {
	if s1 < s2 {
		return true
	}
	if s1 == s2 && m1 < m2 {
		return true
	}
	return false
}

func (skiplist *skiplist) insert(member string, score float64) *node {
	update := make([]*node, maxLevel) // 用于记录新节点在每层需要插入的位置
	rank := make([]int64, maxLevel)   // 用于计算跨过的节点数，即排名

	// 找到各层次的前驱节点
	n := skiplist.header
	for i := skiplist.level - 1; i >= 0; i-- {
		if i == skiplist.level-1 {
			rank[i] = 0
		} else {
			rank[i] = rank[i+1]
		}
		if n.level[i] != nil {
			for n.level[i].forward != nil && compare(n.level[i].forward.Score, score, n.level[i].forward.Member, member) {
				rank[i] += n.level[i].span
				n = n.level[i].forward
			}
		}
		update[i] = n
	}

	level := randomLevel()
	if level > skiplist.level {
		for i := skiplist.level; i < level; i++ {
			rank[i] = 0
			update[i] = skiplist.header
			update[i].level[i].span = skiplist.length
		}
		skiplist.level = level
	}

	// 插入新节点
	n = makeNode(level, score, member)
	for i := int16(0); i < level; i++ {
		n.level[i].forward = update[i].level[i].forward
		update[i].level[i].forward = n

		n.level[i].span = update[i].level[i].span - (rank[0] - rank[i])
		update[i].level[i].span = rank[0] - rank[i] + 1
	}

	// 更新未触及到的节点的跨度
	for i := level; i < skiplist.level; i++ {
		update[i].level[i].span++
	}

	if update[0] == skiplist.header {
		n.backward = nil
	} else {
		n.backward = update[0]
	}
	if n.level[0].forward != nil {
		n.level[0].forward.backward = n
	} else {
		skiplist.tail = n
	}
	skiplist.length++
	return n
}

func (skiplist *skiplist) removeNode(n *node, update []*node) {
	for i := int16(0); i < skiplist.level; i++ {
		if update[i].level[i].forward == n {
			update[i].level[i].span += n.level[i].span - 1
			update[i].level[i].forward = n.level[i].forward
		} else {
			update[i].level[i].span--
		}
	}

	if n.level[0].forward != nil {
		n.level[0].forward.backward = n.backward
	} else {
		skiplist.tail = n.backward
	}
	for skiplist.level > 1 && skiplist.header.level[skiplist.level-1].forward == nil {
		skiplist.level--
	}
	skiplist.length--
}

func (skiplist *skiplist) remove(member string, score float64) bool {
	update := make([]*node, maxLevel)
	n := skiplist.header
	for i := skiplist.level - 1; i >= 0; i-- {
		for n.level[i].forward != nil && compare(n.level[i].forward.Score, score, n.level[i].forward.Member, member) {
			n = n.level[i].forward
		}
		update[i] = n
	}
	n = n.level[0].forward
	if n != nil && n.Score == score && n.Member == member {
		skiplist.removeNode(n, update)
		return true
	}
	return false
}

func (skiplist *skiplist) getByRank(rank int64) *node {
	i := int64(0)
	n := skiplist.header
	for level := skiplist.level - 1; level >= 0; level-- {
		for n.level[level].forward != nil && (i+n.level[level].span) <= rank {
			i += n.level[level].span
			n = n.level[level].forward
		}
		if i == rank {
			return n
		}
	}
	return nil
}

func (skiplist *skiplist) getRank(member string, score float64) int64 {
	rank := int64(0)
	n := skiplist.header
	for i := skiplist.level - 1; i >= 0; i-- {
		for n.level[i].forward != nil && compare(n.level[i].forward.Score, score, n.level[i].forward.Member, member) {
			rank += n.level[i].span
			n = n.level[i].forward
		}

		if n.Member == member {
			return rank
		}
	}
	return 0
}
